import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-03-18
 * Time: 15:17
 */
class Tools {
    static public <T> Set<T> intersection(Set<T> A, Set<T> B) {
        Set<T> C = new HashSet<>();
        A.forEach(v -> {
            if (B.contains(v)) C.add(v);
        });
        return C;
    }

}
class SparseMatrix<T> {
    private Map<Long, Map<Long, T>> matrix;
    private long n, m;

    public SparseMatrix(long n, long m) {
        this.n = n;
        this.m = m;
        this.matrix = new HashMap<>();
    }

    public void append(long i, long j, T value) {
        SparseMatrix.makeMap(i, j, value, matrix);
    }

    static private <T> void makeMap(long i, long j, T v, Map<Long, Map<Long, T>> ref) {
        Map<Long, T> map;
        if ((map = ref.get(i)) != null) {
            map.put(j, v);
        } else {
            map = new HashMap<>();
            map.put(j, v);
            ref.put(i, map);
        }
    }

    /**
     * 矩阵相乘
     *
     * @param A
     * @param B
     * @return result
     */
    static public SparseMatrix<Long> multiply(SparseMatrix<Long> A, SparseMatrix<Long> B) {
        SparseMatrix<Long> result = new SparseMatrix<>(A.n, B.m);
        Map<Long, Map<Long, Long>> bMatrix = B.transpose().matrix, aMatrix = A.matrix;
        aMatrix.forEach((i, mapJ) -> bMatrix.forEach((j, mapI) -> {
            long sum = 0;
            Set<Long> set = Tools.intersection(mapI.keySet(), mapJ.keySet());
            for (Long index : set) sum += aMatrix.get(i).get(index) * bMatrix.get(j).get(index);
            if (sum != 0) SparseMatrix.makeMap(i, j, sum, result.matrix);
        }));
        return result;
    }

    /**
     * 矩阵快速幂
     *
     * @param matrix
     * @param n
     * @return
     */
    static public SparseMatrix<Long> fastPower(SparseMatrix<Long> matrix, Long n) {
        if (n < 0) throw new IndexOutOfBoundsException("n must > 0");
        if (matrix.n != matrix.m) throw new IndexOutOfBoundsException("n != m");
        SparseMatrix<Long> result = new SparseMatrix<>(matrix.n, matrix.m);
        if (n == 0) {
            for (int i = 0; i < matrix.n; i++) result.append(i, i, 1L);
        } else {
            for (Long i : matrix.matrix.keySet()) result.append(i, i, 1L);
        }
        while (n != 0) {
            if (n % 2 == 1) result = SparseMatrix.multiply(result, matrix);
            matrix = SparseMatrix.multiply(matrix, matrix);
            n /= 2;
        }
        return result;
    }

    /**
     * 矩阵相加
     *
     * @param matrixA
     * @param matrixB
     * @return
     */
    static public SparseMatrix<Long> add(SparseMatrix<Long> matrixA, SparseMatrix<Long> matrixB) {
        if (matrixA.n != matrixB.n || matrixA.m != matrixB.m) throw new IndexOutOfBoundsException("error");
        SparseMatrix<Long> result = new SparseMatrix<>(matrixA.n, matrixA.m);
        matrixA.matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
            Map<Long, Long> map;
            if ((map = matrixB.matrix.get(i)) != null) {
                Long valueB;
                if ((valueB = map.get(j)) != null) {
                    SparseMatrix.makeMap(i, j, value + valueB, result.matrix);
                } else {
                    SparseMatrix.makeMap(i, j, value, result.matrix);
                }
            } else {
                SparseMatrix.makeMap(i, j, value, result.matrix);
            }
        }));
        matrixB.matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
            if (result.matrix.get(i) == null) {
                SparseMatrix.makeMap(i, j, value, result.matrix);
            } else if (result.matrix.get(i).get(j) == null) {
                SparseMatrix.makeMap(i, j, value, result.matrix);
            }
        }));
        System.out.println(result);
        return result;
    }

    /**
     * 矩阵转置
     *
     * @return
     */
    public SparseMatrix<T> transpose() {
        SparseMatrix<T> result = new SparseMatrix<>(n, m);
        matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
            SparseMatrix.makeMap(j, i, value, result.matrix);
        }));
        return result;
    }

    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("MATRIX[").append(n).append(", ").append(m).append("]: ");
        long size = 0;
        for (Map.Entry<Long, Map<Long, T>> entry : matrix.entrySet()) {
            Long i = entry.getKey();
            Map<Long, T> map = entry.getValue();
            for (Map.Entry<Long, T> e : map.entrySet()) {
                Long j = e.getKey();
                T value = e.getValue();
                String str = "matrix(" + i + ", " + j + ") = " + value + " ";
                string.append(str);
                size++;
            }
        }
        if (size != n * m) string.append("other matrix(i, j) = 0");
        return string.toString();
    }

}

public class MyMatrix {
    public static void main(String[] args) {
        System.out.println("1");
        System.out.println("2");
    }
}
